/*!
 * \file rdmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Russian doll algorithm for maximum clique.
 */

#include <mcr.h>
#include <heap.h>
#include <stdlib.h>

static int bucketSort1(int * prio, int cmin, int cmax, int * R, int r, int dir) {
	int c = cmax - cmin + 1;
	int b[c];
	int next[r + 1];
	int v[r];
	int i;
	for (i = 0; i < c; i++)
		b[i] = r;
	for (i = 0; i < r; i++) {
		next[i] = b[prio[i] - cmin];
		b[prio[i] - cmin] = i;
		v[i] = R[i];
	}
	int j = 0, k;
	if (dir != 0)
		for (i = 0; j < r; i++) {
			k = b[i];
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
		}
	else
		for (i = c - 1; j < r; i--) {
			k = b[i];
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
		}
	return c;
}

static inline int bucketSort2(int * prio1, int * prio2, int cmin, int cmax,
		int * R, int r, int dir) {

	int inccmp(const void *a, const void *b, void * prio) {
		return ((int *) prio)[*((int *) a)] - ((int *) prio)[*((int *) b)];
	}

	int deccmp(const void *a, const void *b, void * prio) {
		return ((int *) prio)[*((int *) b)] - ((int *) prio)[*((int *) a)];
	}

	int c = cmax - cmin + 1;
	int b[c];
	int next[r + 1];
	int v[r];
	int i;
	for (i = 0; i < c; i++)
		b[i] = r;
	for (i = 0; i < r; i++) {
		next[i] = b[prio1[i] - cmin];
		b[prio1[i] - cmin] = i;
		v[i] = R[i];
	}
	int j = 0, k, l;
	if (dir != 0)
		for (i = 0; j < r; i++) {
			k = b[i];
			l = j;
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
			if (l < j)
				qsort_r(R + l, j - l, sizeof(int), inccmp, prio2);
		}
	else
		for (i = c - 1; j < r; i--) {
			k = b[i];
			l = j;
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
			if (l < j)
				qsort_r(R + l, j - l, sizeof(int), deccmp, prio2);
		}
	return c;
}

int decDegree(Graph * g, int * res) {
	int j;
	int lastnode = NODEIDX(g->n-1);
	int maxdeg = 0, mindeg = g->n;
	int deg[g->n];
	int pos[g->n];
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(NEIG(g, j), 0, lastnode + 1);
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		pos[j] = j;
	}

	// sorts vertices according to degrees
	bucketSort1(deg, mindeg, maxdeg, pos, g->n, 0);
	for (j = 0; j < g->n; j++)
		res[pos[j]] = j;

	return maxdeg;
}

int mcr(Graph * g, int * res) {
	int nelem;
	int nnelem;
	int * next1; // list of keys, level 1; also used in the list of free nodes
	int * next2; // list of keys, level 2
	int * prev1; // list of keys, level 1; also used in the list of free nodes
	int * prev2; // list of keys, level 2
	int * key1; // key, level 1
	int * first3; // first element of the associated list of level 3
	int * node1; // node in the list of level 1

	int freehead; // free nodes of the lists of degrees
	int tailfree; // list of free nodes
	int tail1; // list of level 1
	int tail2; // lists of level 2
	int head1; // head of the list of level 1

	int * next3; // list of keys, level 3
	int * prev3; // list of keys, level 3
	int * key2; // key, level 3
	int * node2; // node in the list of level 2

	int tail3; // lists of level 3

	/*! \fn void removeFree(int j)
	 * \brief Removes a specified node from the list of free nodes
	 *
	 * The specified node is removed from the using the entry associated with it in the arrays
	 * next1 and prev1. freehead is updated if necessary.
	 *
	 * \param j the index of the node to be removed
	 */
	inline void removeFree(int j) {
		next1[prev1[j]] = next1[j];
		prev1[next1[j]] = prev1[j];
		if (j == freehead)
			freehead = next1[j];
	}

	void reset() {
		freehead = 0;
		for (tailfree = 0; tailfree <= nnelem + 1; tailfree++) {
			next1[tailfree] = tailfree + 1;
			prev1[tailfree] = tailfree - 1;
		}
		prev1[0] = --tailfree;
		next1[tailfree] = 0;
		tail1 = tailfree - 1;
		removeFree(tail1);
		head1 = tail1;

		tail2 = tail1 - 1;
		removeFree(tail2);
		tail3 = nelem;
	}

	void initTripleList(int n) {
		nelem = n;
		nnelem = 1 + (n << 1); // an index is left as sentinel

		next1 = (int *) calloc((nnelem << 2) + 8 + (nnelem << 1) + 1,
				sizeof(int));
		next2 = next1 + nnelem + 2;
		prev1 = next2 + nnelem + 2;
		key1 = prev1 + nnelem + 2;
		next3 = key1 + nnelem;
		prev3 = next3 + n + 1;
		key2 = prev3 + n + 1;
		node2 = key2 + n + 1;

		prev2 = prev1;
		node1 = key1;
		first3 = next1;

		reset();
	}

	void delTripleList() {
		free(next1);
	}

	/*! \fn	int comparKey2(int * a, int * b)
	 * \brief Comparison function that specifies the order of level 2 according to \c key2
	 *
	 * The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered
	 * to  be respectively  less  than, equal to, or greater than the second.  If two members compare as equal, their order in the
	 * sorted array is undefined.
	 *
	 * This comparison function is used in functions insertLevel3Backward() and insertLevel3Forward().
	 *
	 * \param a first argument
	 * \param b second argument
	 * \return an integer less than, equal to, or greater than zero if the first argument is considered
	 * to  be respectively  less  than, equal to, or greater than the second
	 */
	inline int comparKey2(int * a, int * b) {
		return *a - *b;
	}

	/*! \fn int removeFreeHead()
	 * \brief Removes an arbitrary node from the list of free nodes
	 *
	 * The returned node is removed from the head of the list. freehead is updated.
	 *
	 * \return a free node, if there is one, or tail12, otherwise.
	 */
	inline int removeFreeHead() {
		int ret = freehead;

		next1[prev1[freehead]] = next1[freehead];
		prev1[next1[freehead]] = prev1[freehead];
		freehead = next1[freehead];

		return ret;
	}

	/*! \fn void addFreeHead(int i)
	 * \brief Adds the specified node to the list of free nodes
	 *
	 * The specified node is added to the head of the list. freehead is updated accordingly.
	 *
	 * \param i the index of the node to be added
	 */
	inline void addFreeHead(int i) {
		prev1[i] = prev1[freehead];
		next1[prev1[freehead]] = i;
		next1[i] = freehead;
		prev1[freehead] = i;
		freehead = i;
	}

	/*! \fn	int insertLevel3Forward(int j, int i)
	 * \brief Inserts the specified node in the list of level 3 associated with node of a list of level 2 of certain key after a
	 * specified node of level 2
	 *
	 * The insertion is performed in the list of level 3 of a node of level 2 *after* the specified basepoint.
	 * This method searches for the node in the list of level 2 until a member corresponding to the specified node's key of level 2
	 * is found or it is detected that such a member does not exist. A new node is inserted in the list of level 2 if necessary.
	 *
	 * Nodes at level 2 are assumed to be ordered in an ascending order of keys determined by comparKey2().
	 *
	 * \param j the basepoint
	 * \param i the node to insert
	 *
	 * \return the node of the list of level 2 that receives the specified node of level 3
	 */
	inline int insertLevel3Forward(int j, int i) {
		int h;
		if (next2[j] != tail2) {
			j = next2[j];
			int c = comparKey2(&key2[first3[j]], &key2[i]);
			while (next2[j] != tail2 && c < 0) {
				j = next2[j];
				c = comparKey2(&key2[first3[j]], &key2[i]);
			}
			if (c == 0)
				h = j;
			else if (next2[j] == tail2 && c < 0) {
				h = j;
				j = tail2;
			} else
				h = prev2[j];
		} else {
			h = j;
			j = tail2;
		}

		if (h == j) {
			next3[i] = first3[j];
			prev3[first3[j]] = i;
			node2[i] = j;
			prev3[i] = tail3;
			first3[j] = i;
		} else {
			int l = removeFreeHead();

			next2[h] = l;
			prev2[l] = h;
			next2[l] = j;
			prev2[j] = l;

			first3[l] = i;
			next3[i] = tail3;
			node2[i] = l;
			prev3[i] = tail3;
			j = l;
		}

		return j;
	}

	/*! \fn	int insertLevel3Backward(int j, int i)
	 * \brief Inserts the specified node in the list of level 3 associated with node of a list of level 2 of certain key after a
	 * specified node of level 2
	 *
	 * The insertion is performed in the list of level 3 of a node of level 2 *after* the specified basepoint.
	 * This method searches for the node in the list of level 2 until a member corresponding to the specified node's key of level 2
	 * is found or it is detected that such a member does not exist. A new node is inserted in the list of level 2 if necessary.
	 *
	 * Nodes at level 2 are assumed to be ordered in an ascending order of keys determined by comparKey2().
	 *
	 * \param j the basepoint
	 * \param i the node to insert
	 *
	 * \return the node of the list of level 2 that receives the specified node of level 3
	 */
	inline int insertLevel3Backward(int j, int i) {
		int h, nd1 = node1[j];
		if (prev2[j] != nd1) {
			j = prev2[j];
			int c = comparKey2(&key2[first3[j]], &key2[i]);
			while (prev2[j] != nd1 && c > 0) {
				j = prev2[j];
				c = comparKey2(&key2[first3[j]], &key2[i]);
			}
			if (c == 0)
				h = j;
			else if (prev2[j] == nd1 && c > 0)
				h = nd1;
			else {
				h = j;
				j = next2[j];
			}
		} else
			h = nd1;

		if (h == j) {
			next3[i] = first3[j];
			prev3[first3[j]] = i;
			node2[i] = j;
			prev3[i] = tail3;
			first3[j] = i;
		} else {
			int l = removeFreeHead();

			next2[h] = l;
			prev2[l] = h;
			next2[l] = j;
			prev2[j] = l;

			first3[l] = i;
			next3[i] = tail3;
			node2[i] = l;
			prev3[i] = tail3;
			j = l;
		}

		return j;
	}

	/*! \fn int insertLevel1Before(int k)
	 *
	 * \brief Inserts a free node in the list of level 1 just before a specified node
	 *
	 * A free node is removed from the free list with removeFreeHead(). head1 is
	 * updated if necessary.
	 *
	 * \param k the node in the list of level 1 before which the free node is inserted
	 *
	 * \return the node removed
	 */
	inline int insertLevel1Before(int k) {
		int j = removeFreeHead();
		next1[prev1[k]] = j;
		prev1[j] = prev1[k];
		prev1[k] = j;
		next1[j] = k;
		if (head1 == k)
			head1 = j;

		return j;
	}

	/*!	\fn int removeLevel1(int j)
	 * \brief Removes the specified node from the list of level 1
	 *
	 * head1 is updated if necessary. The node returned is not added to the list of free nodes.
	 *
	 * \param j the node to be removed
	 *
	 * \return the node inserted
	 */
	inline int removeLevel1(int j) {
		next1[prev1[j]] = next1[j];
		prev1[next1[j]] = prev1[j];
		if (j == head1)
			head1 = next1[j];

		return j;
	}

	/*! \fn int removeLevel2(int j)
	 * \brief Removes the specified node from the list of level 2
	 *
	 * List of level 1 is updated if its node heading the list of level 2 conatining the specified node becomes empty.
	 * If a node is removed from the list of level 1, then it is added
	 * to the list of free nodes with addFreeHead().
	 *
	 * The node returned is not added to the list of free nodes.
	 *
	 * \param j the node to be removed
	 *
	 * \return the node removed
	 */
	inline int removeLevel2(int j) {
		next2[prev2[j]] = next2[j];
		prev2[next2[j]] = prev2[j];

		if (next2[node1[j]] == tail2) {
			removeLevel1(node1[j]);
			addFreeHead(node1[j]);
		}

		return j;
	}

	/*! \fn	int removeLevel3Of(int j)
	 * \brief Removes a node from the list of level 3 associated with the specified node of a list of level 2
	 *
	 * If the list of level 3 involved in this operation becomes empty, then the specified node is removed from its list of
	 * level 2 and added to the list of free nodes. In this case, if the corresponding node in the list of level 1 also becomes
	 * empty, then it is removed and added to the list of free nodes.
	 *
	 * \param j a node of a list of level 2
	 *
	 * \return the node removed
	 */
	inline int removeLevel3Of(int j) {
		int i = first3[j];
		first3[j] = next3[i];

		if (first3[j] == tail3) {
			removeLevel2(j);
			addFreeHead(j);
		}

		return i;
	}

	/*! \fn	int removeLevel3(int i)
	 * \brief Removes the specified node from the list of level 3
	 *
	 * If the list of level 3 involved in this operation becomes empty, then the corresponding node is removed from its list of
	 * level 2 and added to the list of free nodes.
	 *
	 * No nodes are removed from the list of level 1.
	 *
	 * \param i a node of a list of level 3
	 *
	 * \return the node of the list of level 1 corresponding to the node of level 3 removed
	 */
	inline int removeLevel3(int i) {
		int j = node2[i];
		int ret = node1[j];
		if (first3[j] == i) {
			first3[j] = next3[i];
			prev3[first3[j]] = tail3;
			if (first3[j] == tail3) {
				next2[prev2[j]] = next2[j];
				prev2[next2[j]] = prev2[j];
				addFreeHead(j);
			}
		} else {
			next3[prev3[i]] = next3[i];
			prev3[next3[i]] = prev3[i];
		}

		return ret;
	}

	inline void printLevel3(int v2) {
		int v3 = first3[v2];
		printf(" [key2=%d:", key2[v3]);
		while (v3 != tail3) {
			printf(" %d", v3);
			v3 = next3[v3];
		}
		printf("]");
	}

	inline void printLevel2(int v1) {
		printf("key1=%d", key1[v1]);
		int v2 = next2[v1];
		while (v2 != tail2) {
			printLevel3(v2);
			v2 = next2[v2];
		}
		printf("\n");
	}

	inline void print() {
		int v1 = head1;
		while (v1 != tail1) {
			printLevel2(v1);
			v1 = next1[v1];
		}
	}

	int v, u;
	int j;

	//initializes the vector of degrees
	initTripleList(g->n);
	int lastnode = NODEIDX(g->n-1);
	int maxdeg = 0, mindeg = g->n;
	for (j = 0; j < g->n; j++) {
		removeFree(j);
		key1[j] = cardOfSet(NEIG(g, j), 0, lastnode + 1);
		if (key1[j] > maxdeg)
			maxdeg = key1[j];
		if (key1[j] < mindeg)
			mindeg = key1[j];
		res[j] = j;
	}

	// sorts vertices according to degrees
	bucketSort1(key1, mindeg, maxdeg, res, g->n, 1);

	//initializes the vector of ex-degrees
	int nodeidx;
	for (j = 0; j < g->n; j++) {
		key2[j] = 0;
		nodeidx = 0;
		u = NODELEAST(NEIG(g, j)[nodeidx]);
		while (u < 0 && nodeidx < lastnode)
			u = NODELEAST(NEIG(g, j)[++nodeidx]);
		while (u >= 0) {
			key2[j] += key1[NELEM(nodeidx) + u];
			u = NODENEXTLEAST(NEIG(g, j)[nodeidx],u);
			while (u < 0 && nodeidx < lastnode)
				u = NODELEAST(NEIG(g, j)[++nodeidx]);
		}
	}

	// sorts vertices according to degrees
	head1 = res[0];
	next1[head1] = tail1;
	prev1[head1] = tail1;
	next1[tail1] = head1;
	prev1[tail1] = head1;
	next2[head1] = tail2;
	next2[tail1] = tail2;

	int current1 = head1;
	prev2[tail2] = current1;
	node1[tail2] = current1;
	v = insertLevel3Backward(tail2, res[0]);
	node1[v] = current1;
	for (j = 1; j < g->n; j++) {
		if (key1[res[j]] == key1[current1])
			addFreeHead(res[j]);
		else {
			next1[res[j]] = next1[current1];
			prev1[next1[current1]] = res[j];
			next1[current1] = res[j];
			prev1[res[j]] = current1;
			current1 = res[j];
			next2[current1] = tail2;
			v = current1;
			prev2[tail2] = current1;
			node1[tail2] = current1;
		}
		v = insertLevel3Backward(next2[v], res[j]);
		node1[v] = current1;
	}

	//sorting
	NODETYPE bitvector[lastnode + 1];
	ADDALL(bitvector, lastnode+1);
	int i = g->n;
	while (--i >= 0) {
		//color the first in the heap
		v = removeLevel3Of(next2[head1]);
		bitvector[NODEIDX(v)] = DELFROMNODE(bitvector[NODEIDX(v)], IDXINNODE(v));
		res[v] = i; //g->n-i-1;

		int unodeidx = 0;
		int uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
		while (uidx < 0 && unodeidx < lastnode) {
			++unodeidx;
			uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
		}
		while (uidx >= 0) {
			int u = NELEM(unodeidx) + uidx;
			int keyu = key1[node1[node2[u]]] - 1;
			int wnodeidx = 0;
			int w, y;
			int widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
			while (widx < 0 && wnodeidx < lastnode) {
				++wnodeidx;
				widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
			}
			while (widx >= 0) {
				w = NELEM(wnodeidx) + widx;
				int nd2 = node2[w];
				int pnd2 = prev2[nd2];
				if (first3[nd2] == w && next3[w] == tail3)
					y = next2[nd2];
				else
					y = nd2;
				int z = removeLevel3(w);
				key2[w]--;
				prev2[tail2] = pnd2;
				node1[tail2] = node1[nd2];
				y = insertLevel3Backward(y, w);
				node1[y] = z;
				widx =
						NODENEXTLEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx],widx);
				while (widx < 0 && wnodeidx < lastnode) {
					++wnodeidx;
					widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
				}
			}

			y = removeLevel3(u);
			w = next1[y];
			int s = key1[y];
			if (next2[y] == tail2) {
				removeLevel1(y);
				addFreeHead(y);
				y = w;
			}
			if (y == head1 || key1[prev1[y]] < s - 1) {
				y = insertLevel1Before(y);
				next2[y] = tail2;
				key1[y] = s - 1;
			} else
				y = prev1[y];
			w = y;
			key2[u] -= keyu;
			y = insertLevel3Forward(y, u);
			node1[y] = w;
			uidx =
					NODENEXTLEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx],uidx);
			while (uidx < 0 && unodeidx < lastnode) {
				++unodeidx;
				uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
			}
		}
	}

	delTripleList();
	return maxdeg;
}

int decExdegree(Graph * g, int * res) {
	int u;
	int j;

	int deg[g->n];
	int exdeg[g->n];
	int pos[g->n];

	//initializes the vector of degrees
	int lastnode = NODEIDX(g->n-1);
	int maxdeg = 0, mindeg = g->n;
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(NEIG(g, j), 0, lastnode + 1);
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		pos[j] = j;
	}

	//initializes the vector of ex-degrees
	int nodeidx;
	for (j = 0; j < g->n; j++) {
		exdeg[j] = 0;
		nodeidx = 0;
		u = NODELEAST(NEIG(g, j)[nodeidx]);
		while (u < 0 && nodeidx < lastnode)
			u = NODELEAST(NEIG(g, j)[++nodeidx]);
		while (u >= 0) {
			exdeg[j] += deg[NELEM(nodeidx) + u];
			u = NODENEXTLEAST(NEIG(g, j)[nodeidx],u);
			while (u < 0 && nodeidx < lastnode)
				u = NODELEAST(NEIG(g, j)[++nodeidx]);
		}
	}

	// sorts vertices according to degrees
	bucketSort2(deg, exdeg, mindeg, maxdeg, pos, g->n, 0);
	for (j = 0; j < g->n; j++)
		res[pos[j]] = j;

	return maxdeg;
}

int heapMcr(Graph * g, int * ret) {
	int u;
	int j;

	int * deg = calloc(g->n << 2, sizeof(int));
	int * exdeg = deg + g->n;
	int * pos = exdeg + g->n;
	int * res = pos + g->n;

	//initializes the vector of degrees
	int lastnode = NODEIDX(g->n-1);
	int maxdeg = 0, mindeg = g->n;
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(NEIG(g, j), 0, lastnode + 1);
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		res[j] = j;
		pos[j] = j;
	}

	//initializes the vector of ex-degrees
	int nodeidx;
	for (j = 0; j < g->n; j++) {
		exdeg[j] = 0;
		nodeidx = 0;
		u = NODELEAST(NEIG(g, j)[nodeidx]);
		while (u < 0 && nodeidx < lastnode)
			u = NODELEAST(NEIG(g, j)[++nodeidx]);
		while (u >= 0) {
			exdeg[j] += deg[NELEM(nodeidx) + u];
			u = NODENEXTLEAST(NEIG(g, j)[nodeidx],u);
			while (u < 0 && nodeidx < lastnode)
				u = NODELEAST(NEIG(g, j)[++nodeidx]);
		}
	}

	int deccmp(const void *a, const void *b) {
		int ret = deg[*((int *) a)] - deg[*((int *) b)];
		return ret == 0 ? exdeg[*((int *) a)] - exdeg[*((int *) b)] : ret;
	}

	int hash(const void * x) {
		return *((int *) x);
	}

	heapify_a(pos, g->n, sizeof(int), deccmp, res, hash);

	int x, v, w;
	NODETYPE bitvector[lastnode + 1];
	ADDALL(bitvector, lastnode+1);

//	printf("[ ");
	for (x = 0, j = g->n; x < g->n; x++) {
		v = pos[0];
		ret[v] = --j;
		heappoll_a(pos, g->n - x, sizeof(int), deccmp, res, hash);

//		printf(" %d:%d:%d:%d", v,pos[v],deg[v],exdeg[v]);

		bitvector[NODEIDX(v)] = DELFROMNODE(bitvector[NODEIDX(v)], IDXINNODE(v));
		int unodeidx = 0;
		int uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
		while (uidx < 0 && unodeidx < lastnode) {
			++unodeidx;
			uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
		}
		while (uidx >= 0) {
			u = NELEM(unodeidx) + uidx;
			deg[u]--;

			heapdown_a(pos, res[u], g->n - x - 1, sizeof(int), deccmp, res,
					hash);

			int wnodeidx = 0;
			int widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
			while (widx < 0 && wnodeidx < lastnode) {
				++wnodeidx;
				widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
			}
			while (widx >= 0) {
				w = NELEM(wnodeidx) + widx;
				exdeg[w]--;

				heapdown_a(pos, res[w], g->n - x - 1, sizeof(int), deccmp, res,
						hash);

				widx =
						NODENEXTLEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx],widx);
				while (widx < 0 && wnodeidx < lastnode) {
					++wnodeidx;
					widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
				}
			}

			uidx =
					NODENEXTLEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx],uidx);
			while (uidx < 0 && unodeidx < lastnode) {
				++unodeidx;
				uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
			}
		}
	}
//	printf(" ]\n");
	free(deg);

	return maxdeg;
}
